package com.hy.study.stack;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

/**
 * 逆波兰表达式
 */
public class PolandNotation {
    public static void main(String[] args) {
        //(3+4)*5-6 的逆波兰表达式 3 4 + 5 x 6 -
        //(30+4)*5-6 的逆波兰表达式 30 4 + 5 x 6 -
        String experssion = "(30+4)x5-6";
        List<String> epL = toInfixExpressionList(experssion);
        System.out.println(epL);
        List<String> rpn = parseSuffixExpersssionList(epL);
       // System.out.println(epL+"后缀表示:"+list);

        //String suffixExperssion = "30 4 + 5 x 6 -";
        //为了方便取值 字符之间添加空格
        //List<String> rpn = getListString(suffixExperssion);
        int result = calculate(rpn);
        System.out.printf("后缀表达式:%s 计算结果为:%d", experssion, result);

    }

    /**
     * 将中缀表达式list 转换成后缀表达式 list
     *
     * @param list
     * @return
     */
    public static List<String> parseSuffixExpersssionList(List<String> list) {
        Stack<String> stack = new Stack<>();
        ArrayList<String> resultList = new ArrayList<>();
        for (String item : list) {
            //如果是一个数 加入到resultList
            if (item.matches("\\d+")) {
                resultList.add(item);
            } else if ("(".equals(item)) {//如果是一个(
                stack.push(item);
            } else if (")".equals(item)) {
                //一次弹出 stack 一直弹到(
                while (!stack.peek().equals("(")) {
                    resultList.add(stack.pop());
                }
                stack.pop();//消掉一对() 将( 弹出
            } else {
                //当item 的优先级小于等于 栈顶运算符的优先级，
                while (stack.size() != 0 && Operation.getValue(stack.peek()) >= Operation.getValue(item)) {
                    resultList.add(stack.pop());
                }
                //将item 压入到栈中
                stack.push(item);
            }
        }
        //将 栈中的所有数据加入到 ResultList
        while (stack.size()!=0){
            resultList.add(stack.pop());
        }
        //因为是存放在list中，所以顺序输出就是逆波兰表达式  如果是栈 需要倒序输出
        return resultList;


    }


    public static List<String> toInfixExpressionList(String s) {
        ArrayList<String> list = new ArrayList<>();
        int i = 0;
        String str;
        char ch;
        do {
            ch = s.charAt(i);
            if (ch < 48 || ch > 57) {//不是数字
                list.add("" + ch);
                i++;
            } else {
                //如果是数字 需要考虑多位数问题
                str = "";
                while (i < s.length() && (ch = s.charAt(i)) >= 48 && (ch = s.charAt(i)) <= 57) {
                    str += ch;
                    i++;
                }
                list.add(str);
            }
        } while (i < s.length());
        return list;
    }

    public static List<String> getListString(String suffixException) {
        String[] split = suffixException.split(" ");
        ArrayList<String> arrayList = new ArrayList<>();
        for (String ch : split) {
            arrayList.add(ch);
        }
        return arrayList;
    }

    public static int calculate(List<String> ls) {
        Stack<String> stack = new Stack<>();
        for (String item : ls) {
            if (item.matches("\\d+")) {//匹配多位数
                stack.push(item);
            } else {
                //如果是运算符 pop 两个数 在运算
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int result = 0;
                if ("+".equals(item)) {
                    result = num1 + num2;
                } else if ("-".equals(item)) {
                    result = num1 - num2;
                } else if ("x".equals(item)) {
                    result = num1 * num2;
                } else if ("/".equals(item)) {
                    result = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                stack.push(result + "");
            }
        }

        return Integer.parseInt(stack.pop());

    }

}

class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    public static int getValue(String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
            case "x":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("运算符错误" + operation);
        }
        return result;
    }
}